Unique substrings in wraparound string

Time: O(N); Space: O(1); medium

Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: p = “a”

Output: 1

Explanation:

  • Only the substring “a” of string “a” is in the string s.

Example 2:

Input: p = “cac”

Output: 2

Explanation:

  • There are two substrings “a”, “c” of string “cac” in the string s.

Example 3:

Input: p = “zab”

Output: 6

Explanation:

  • There are six substrings “z”, “a”, “b”, “za”, “ab”, “zab” of string “zab” in the string s.

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def findSubstringInWraproundString(self, p):
        """
        :type p: str
        :rtype: int
        """
        letters = [0] * 26
        result, length = 0, 0

        for i in range(len(p)):
            curr = ord(p[i]) - ord('a')
            if i > 0 and ord(p[i-1]) != (curr-1) % 26 + ord('a'):
                length = 0
            length += 1
            if length > letters[curr]:
                result += length - letters[curr]
                letters[curr] = length

        return result

[4]:

s = Solution1()

p = "a"
assert s.findSubstringInWraproundString(p) == 1

p = "cac"
assert s.findSubstringInWraproundString(p) == 2

p = "zab"
assert s.findSubstringInWraproundString(p) == 6